package com.kjc.demo.basic.algorithmtest;

public class Test0927 {
	//冒泡排序
	public void  bubbleSort(int[] arr) {
		for(int i=0; i< arr.length -1;i ++) {
			for(int j=0;j<arr.length - i - 1; j++) {
				if(arr[j] > arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}
	//选择排序
	public void selectSort(int[] arr) {
		for(int i=0;i< arr.length-1; i++) {
			int min = i;
			for(int j = i+1;j<arr.length-1;j++) {
				if(arr[j] < arr[min]) {
					min = j;
				}
			}
			if(min != i) {
				int temp = arr[i];
				arr[i] = arr[min];
				arr[min] = temp;
			}
		}
	}
	//插入排序
	public void insertSort(int[] arr) {
		for(int i = 1; i < arr.length ; i++) {
			if(arr[i] < arr[i-1]) {
				int j = i;
				while(j >= 0 && arr[j] < arr[j-1]) {
					int temp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = temp;
					j--;
				}
			}
		}
	}
	//快速排序
	public void quickSort(int[] arr,int start,int end) {
		int i=start;//左边下标
		int j = end;//右边下标
		int pre = arr[start];//起始元素
		while(i < j) {//循环条件
			while(i < j && arr[j] > pre) {//
				j--;
			}
			
			while(i < j && arr[i] < pre ) {
				i++;
			}
			
			if(i<j && arr[i] == arr[j]) {
				i++;
			}else {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = arr[i];
			}
		}
		if(i-1 > start) {
			quickSort(arr,start ,i-1);
		}
		if(i+1 < end) {
			quickSort(arr,i+1,end);
		}
	}
	//希尔排序
	public void shellSort(int[] arr) {
		for(int gap = arr.length/2-1; gap > 0; gap=gap/2) {
			for(int i = gap;i<arr.length;i++) {
				int j = i;
				while(j-gap>=0 && arr[j] < arr[j-gap]) {
					int temp = arr[j];
					arr[j] = arr[j-gap];
					arr[j-gap] = temp;
					j=j-gap;
				}
			}
		}
	}
	//归并排序
	//基数排序
	//堆排序
	public void heapSort(int[] arr) {
		// 构建大顶堆
		for(int i=arr.length/2-1;i >= 0; i--) {
			adjustHeap(arr,i,arr.length);
		}
		
		//交换堆顶和末尾元素
		for(int j = arr.length - 1; j > 0 ; j--) {
			int temp = arr[0];
			arr[0] = arr[j];
			arr[j] = temp;
			//重新构建大顶堆
			adjustHeap(arr, 0, j);
		}
	}
	
	public void adjustHeap(int[] arr,int i,int length) {
		int temp = arr[i];
		for(int k = 2*i+1;i<length;k=k*2+1) {
			if(k+1<length && arr[k] < arr[k+1]) {
				k++;
			}
			
			if(arr[k] > temp) {
				arr[i] = arr[k];
				i = k;
			}else {
				break;
			}
		}
		arr[i] = temp;
		
	}
}
